Binary multiplication is just like decimal multiplication, it’s just a bunch of addition.
\begin{align*} &110 \\ \times &101 \end{align*}
—is equal to—
\begin{align*} &110 \\ 0&00 \\ + 11&0 \\ = 11&110 \end{align*}
This is also known as partial product summation, and it requires a lot of addition.
Compressor:
Note: Compressors are basic components in a lot of applications, like ones for multiplication.
Example: Is it possible to create a 15-4 multiplier?
- Reword: Can you represent the result adding 15 bits with 4 bits?
- The biggest number you can get is 15_{10}, the biggest number you can represent with 4 bits is 2n-1 = 16 - 1 = 15, so yes.
Advanced Compressor:
More on Carry Behavior: Carry bits aren’t compressed because they’ll be generated and consumed by whatever circuit design uses advanced compressors.
Easy and slow.
Very efficient.
Let M and d be two numbers.
\frac{M}{d} = \frac{0.M}{0.d}, y = 1 - 0.d \to 0.d = 1 - y
Base Formula:
\frac{0.M}{0.d} &= \frac{0.M}{1 - y}
Now, we can multiply numerator and denominator by (1+y) repeatedly, the more repetitions, the more accurate the approximation will be
\begin{align*} \frac{0.M}{1 - y} &= \frac{0.M (1 + y)}{(1-y)(1+y)} = \frac{0.M (1 + y)}{1 - y^2} \\ &= \frac{0.M (1+y)(1+y^2)}{(1-y^2)(1+y^2)} = \frac{0.M (y)(1+y^2)}{(1-y^4)} \end{align*}